#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2020/6/6 17:57
# @USER    : Shengji He
# @File    : SwapNodesPairs.py
# @Software: PyCharm
# @Version  : Python-
# @TASK:

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        """
        Given a linked list, swap every two adjacent nodes and return its head.

        You may not modify the values in the list's nodes, only nodes itself may be changed.

        Example:

        Given 1->2->3->4, you should return the list as 2->1->4->3.

        :param head: ListNode
        :return: ListNode
        """
        # if not head or head.next is None:
        #     return head
        # ans = node = ListNode(0)
        #
        # while head.next:
        #     node.next = head.next
        #     node = node.next
        #     head.next = head.next.next
        #     node.next = head
        #     if head.next:
        #         head = head.next
        #     else:
        #         break
        #     node = node.next
        #
        # return ans.next

        # If the list has no node or has only one node left.
        if not head or not head.next:
            return head

        # Nodes to be swapped
        first_node = head
        second_node = head.next

        # Swapping
        first_node.next  = self.swapPairs(second_node.next)
        second_node.next = first_node

        # Now the head is the second node
        return second_node


if __name__ == '__main__':
    S = Solution()
    # input1 = [1, 2, 3, 4, 5]
    input1 = [1, 2, 3, 4]
    # input1 = [1]
    print(input1)
    l1 = ListNode(input1.pop(0))
    temp1 = l1
    for element in input1:
        temp1.next = ListNode(element)
        temp1 = temp1.next
    output = S.swapPairs(l1)
    print('done')
